<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        /**
         * 
         * 不同子序列
           输入：s = "ahbgdc", t = "abc"
           输出：false
           解释：判断在s的子序列中出现的t的个数
           分析：动态规划

           dp[i][j]：表示以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]
        */
        /* 
            时间：O(n * m)
            空间：O(n * m)
        */
        // 动态规划
        var numDistinct = function(s, t) {
            let sLen = s.length;
            let jLen = t.length;
            // 初始化dp数组
            let dp = Array.from(Array(s.length + 1), () => Array(t.length +1).fill(0));
            // dp[i][0]初始化为1
            // dp[0][j]初始化为0
            for (let i = 0; i < sLen + 1; i++) {
                dp[i][0] = 1
            }

            for (let i = 1; i <= sLen; i++) {
                for (let j = 1; j <= jLen; j++) {
                    if (s[i - 1] === t[j - 1]) {
                        dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
                    } else {
                        dp[i][j] = dp[i - 1][j]
                    }
                }
            }
            console.log(dp, 'dp');
            return dp[sLen][jLen]
        };
        // console.log(numDistinct('rabbbit', 'rabbit'));
        console.log(numDistinct('babgbag', 'bag'));
    </script>
</body>

</html>